/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
 * <p>
 * 重叠区间的个数统计
 * Example 1: 
 * Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 * Example 2: 
 * Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as
 * [1,2],[3,10],[12,16].
 * 
 * This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月21日
 */
public class InsertInterval {

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<>();
        if(intervals==null){
            //输入是Null，那么在奇偶空额返回新区间
            result.add(newInterval);
            return result;
        }
        int i=0;
        int n = intervals.size();
        while(i<n && newInterval.start>intervals.get(i).end){
            //加入非重叠的区间
            result.add(intervals.get(i++));
        }
        
        while(i<n && newInterval.end>= intervals.get(i).start){
            //合并重叠区间到新的区间
            newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
            newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
            i++;
        }
        //加上合并后的新区间
        result.add(newInterval);
        //加上剩余部分，如果有
        while(i<n){
            result.add(intervals.get(i++));
        }
        return result;
    }
    
    @Test
    public void testCase1(){
        Interval newInterval = new Interval(4, 6) ;
        
        List<Interval> intervals = new ArrayList<>();
        Interval newInterval1 = new Interval(1, 5) ;
        Interval newInterval2 = new Interval(6, 10) ;
        intervals.add(newInterval1);
        intervals.add(newInterval2);
        
        List<Interval> insert = insert(intervals, newInterval);
        System.out.println(insert);
    }
}
